题解 P1948 [USACO08JAN]电话线Telephone Lines

发表于 | 更新于

题意:求原点$1$到$n$的所有路中的第$k+1$长的路最小

二分答案+$spfa$

题意：求原点$1$到$n$的所有路中的第$k+1$长的路最小。

因为题意中的答案要最小，我们贪心肯定要使$k$次免费的资格用完，那么最划算的方案肯定是拿最长的$k$条路使之免费，然后付第$k+1$长路的长度的钱。。。这样的贪心思路显然是正确的。

我们首先二分第$k+1$长的路的长度(即答案)，然后关键是如何判断正确性。我们考虑简化问题，对于长度小于二分出的答案的线段，因为不需要付价钱，所以可以将其权值看作是$0$;同理，大于二分的值的路径，我们将长度看作$1$(意味着我需要使用$1$次免费的资格)。我们跑一遍$spfa$，看到了$n$点的最短路的长度，如果大于$k$，则不行，缩小$r$范围继续二分;如果小于，则有可能更小，缩小$l$范围继续二分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
#define ll long long
#define sqr(x) ((x)*(x))
using namespace std;
struct node{
    int dis,to,next;
    bool operator <(const node &x)const{
        return x.dis<dis;
    }
}e[400000];
int n,m,k,o,head[400000],cnt,dis[400000],vis[400000],u[400000],w[400000],v[400000];
inline void add(int u,int v,int d){
    e[++cnt].dis=d;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
inline int read(){
   int x=0,w=0;char ch=getchar();
   while (!isdigit(ch))w|=ch=='-',ch=getchar();
   while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
   return w?-x:x;
}
priority_queue<node>q;
bool dijkstra(){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[1]=0;
    q.push(node{0,1});
    while (!q.empty()){
        int x=q.top().to;q.pop();
        if (vis[x])continue;
        vis[x]=1;
        for (int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if (dis[y]>dis[x]+e[i].dis){
                dis[y]=dis[x]+e[i].dis;
                q.push(node{dis[y],y});
            }
        }
    }
    if (dis[n]>k)
        return 0;
    else{o=1;return 1;}
}
int main(){
    n=read(),m=read(),k=read();
    for (int i=1;i<=m;++i)
        u[i]=read(),v[i]=read(),w[i]=read();
    int l=0,r=1000000;
    while (l<r){
        int mid=l+r>>1;
        memset(head,0,sizeof(head));cnt=0;
        for (int i=1;i<=m;++i)add(u[i],v[i],mid<w[i]),add(v[i],u[i],mid<w[i]);
        if (dijkstra())r=mid;
        else l=mid+1;
    }
    if (o)printf("%d\n",l);
    else puts("-1");
    return 0;
}